


public class Solution {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 确保 p.val 小于 q.val
        if (p.val > q.val) {
            TreeNode temp = p;
            p = q;
            q = temp;
        }

        while (root != null) {
            // 如果 p 和 q 的值都小于 root，则向左子树遍历
            if (p.val < root.val && q.val < root.val) {
                root = root.left;
            }
            // 如果 p 和 q 的值都大于 root，则向右子树遍历
            else if (p.val > root.val && q.val > root.val) {
                root = root.right;
            } else {
                // 否则，当前节点就是最近公共祖先
                return root;
            }
        }
        return null; // 如果树为空，返回null
    }


    public TreeNode lowestCommonAncestor(TreeNode root, int o1, int o2) {
        // 如果当前节点为空，或者当前节点是o1或o2之一，则返回当前节点
        if (root == null || root.val == o1 || root.val == o2) {
            return root;
        }

        // 在左子树中寻找o1和o2的最近公共祖先
        TreeNode left = lowestCommonAncestor(root.left, o1, o2);

        // 在右子树中寻找o1和o2的最近公共祖先
        TreeNode right = lowestCommonAncestor(root.right, o1, o2);

        // 如果o1和o2分别在当前节点的左右子树中，则当前节点即为最近公共祖先
        if (left != null && right != null) {
            return root;
        }

        // 否则，返回非空的那个子树
        return left != null ? left : right;
    }
}
